{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Airplane Seat Assignment Probability"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #brainteaser #math #dynamic-programming #probability-and-statistics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #脑筋急转弯 #数学 #动态规划 #概率与统计"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: nthPersonGetsNthSeat"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #飞机座位分配概率"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有 <code>n</code> 位乘客即将登机，飞机正好有 <code>n</code> 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。</p>\n",
    "\n",
    "<p>剩下的乘客将会：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>\n",
    "\t<p>如果他们自己的座位还空着，就坐到自己的座位上，</p>\n",
    "\t</li>\n",
    "\t<li>当他们自己的座位被占用时，随机选择其他座位</li>\n",
    "</ul>\n",
    "\n",
    "<p>第 <code>n</code>&nbsp;位乘客坐在自己的座位上的概率是多少？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>1.00000\n",
    "<strong>解释：</strong>第一个人只会坐在自己的位置上。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 2\n",
    "<strong>输出:</strong> 0.50000\n",
    "<strong>解释：</strong>在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10^5</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [airplane-seat-assignment-probability](https://leetcode.cn/problems/airplane-seat-assignment-probability/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [airplane-seat-assignment-probability](https://leetcode.cn/problems/airplane-seat-assignment-probability/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        else:\n",
    "            return 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        if n>1:\n",
    "            return 0.5\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1 if n == 1 else 0.5\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1.0 if n == 1 else 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1.0 if n == 1 else 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1 if n == 1 else 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1 if n == 1 else 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1.0 if n == 1 else 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1 if n==1 else .5\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1 if n == 1 else 0.5\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1.0 if n == 1 else 0.5\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        if n == 1:\n",
    "            return 1.0\n",
    "        return 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1 if n==1 else 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1 if n==1 else .5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        else:\n",
    "            return 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        if n == 1:\n",
    "            return 1.0\n",
    "        else:\n",
    "             return 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1 if n==1 else 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1.0 if n == 1 else 0.5\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        # p(n) is the possibility of the last one sitting to his seat under n condition\n",
    "        # p(n) = (1+sumi=2_n-1(p(n-i+1))) / n\n",
    "        # p(n-1) = (1+sumi=2_n-2(p(n-i))) / (n-1)\n",
    "        # np(n) = p(n-1) + (n-1)p(n-1)\n",
    "        # p(n)=...=p(2)\n",
    "        return 0.5 if n>=2 else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n):\n",
    "        if n < 3:\n",
    "            return 1 / n\n",
    "        else:\n",
    "            return 1 / 2\n",
    "'''\n",
    "循环算法\n",
    "if n<3:\n",
    "    return 1/n\n",
    "else:\n",
    "    a = 1/2\n",
    "    for i in range(3,n+1):\n",
    "        a = 1 / i + (i-2) / i * a\n",
    "    return a\n",
    "#递归\n",
    "if n < 3:\n",
    "    return 1/n\n",
    "else:\n",
    "    return 1/n + (n-2) / n * nthPersonGetsNthSeat(n-1)\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        if n <= 2:\n",
    "            return 1/n\n",
    "        fn = 0.5\n",
    "        for i in range(3, n+1):\n",
    "            fn = 1/i + (i-2)/i * fn\n",
    "        return fn\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1.0 if n == 1 else 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        if n < 3:\n",
    "            return 1 / n\n",
    "\n",
    "        a, b = 1, 1/2\n",
    "\n",
    "        for i in range(3, n+1):\n",
    "            a = b\n",
    "            b = 1/i + b*(i-2)/i\n",
    "\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1 if n==1 else 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        else:\n",
    "            return 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1 if n==1 else .5\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        if n == 1:\n",
    "            return 1.0\n",
    "        else:\n",
    "             return 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1 if n==1 else .5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "\n",
    "        return 1 if n == 1 else 0.5\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        if n<=2:\n",
    "            return 1/n\n",
    "        prob=0.5\n",
    "        for i in range(3,n+1):\n",
    "            prob=(1+(i-2)*prob)/i\n",
    "        return prob"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1 if n == 1 else 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        if n == 1:\n",
    "            return 1/n\n",
    "        return n/2/n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        if n<=2:\n",
    "            return 1/n\n",
    "        else:\n",
    "            p = 1/2 \n",
    "            for i in range(3, n+1):\n",
    "                p = 1/i + (i-2)/i * p \n",
    "        \n",
    "        return p  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        if n == 1: return 1\n",
    "        return 1 / 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        if n == 1:\n",
    "            return 1.0\n",
    "        else:\n",
    "            return 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        return 1 / 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1 if n==1 else 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1.0 if n == 1 else 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        else:\n",
    "            return 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1.0 if n == 1 else 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        if n==1:return 1\n",
    "        return 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        return 1 / 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1 if n == 1 else .5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1.0 if n == 1 else 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        return 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1 if n == 1 else 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 0.5 if n > 1 else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        if n <= 2:\n",
    "            return 1/n\n",
    "        sn = 0.5  # n=2\n",
    "        for i in range(3, n+1):\n",
    "            sn = 1/i + (i-2)/i * sn\n",
    "        return sn\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1.0 if n == 1 else 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 当n>=2时\n",
    "# 若第1位乘客选择第i个位置，那么第i位乘客将不能坐到自己的位置\n",
    "# 假设第n位乘客坐在自己位置上的概率为f(n)\n",
    "# 当第1位乘客选择第1个位置时,第n位乘客坐在自己位置上的概率为1/n\n",
    "# 当第1位乘客选择第i个位置时,可看作乘客减少了i-1位 # i - 2 的人按位置做好\n",
    "#    重新编排后，第i位乘客变成第1位乘客，第n位乘客变成第n-i+1位乘客 # 因为前i-1的人已经坐好位置了，第i位的人没有位置那就乱坐 第i位相当于第一个乱坐的人了 这样就缩小规模了\n",
    "#    原第n位乘客坐在自己位置上的概率为1/n*f(n-i+1)\n",
    "# 第1位乘客选择的位置都是等概率的\n",
    "# 所以第n位乘客坐在自己位置上的概率为 1/n + Σ1/n*f(n-i+1)(i=2->n-1)\n",
    "# f(n) = 1/n * (f(n-1)+f(n-2)+f(n-3)+...+f(2)+1)\n",
    "# f(n+1) = 1/(n+1)*(f(n)+f(n-1)+f(n-2)+f(n-3)+...+f(2)+1)\n",
    "# f(n+1) = 1/(n+1)*(f(n)+n*f(n))\n",
    "# f(n+1) = f(n)\n",
    "# 当n>=2时, f(n)=f(2)=0.5\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1 if n == 1 else 0.5\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        # k = 0\n",
    "        # for i in range(2,n+1):\n",
    "        #     k += 1/i\n",
    "\n",
    "        # return 1 - k\n",
    "\n",
    "\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        return 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1 if n == 1 else 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthPersonGetsNthSeat(self, n: int) -> float:\n",
    "        return 1 if n == 1 else 0.5\n",
    "\n",
    "\n",
    "#换一种思路： 后面每一个人来了之后如果自己的座位上有人就把他赶走 所以2~n-1号就会对位入座。 1号就在1和n号之间以50的概率坐下。"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
